import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;

/**
 * 哈希
 */
public class Main5 {

    /**
     * 两数之和
     */
    public int[] twoSum (int[] numbers, int target) {
        // write code here
        int[] arr = new int[0];
        //创建哈希表，两元组分别表示值、下标
        HashMap<Integer, Integer> hash = new HashMap<>();
        //在哈希表中查找target-numbers[i];
        for(int i = 0; i < numbers.length; i++) {
            int tmp = target - numbers[i];
            //若是没找到，将此信息记入哈希表
            if(!hash.containsKey(tmp)) {
                hash.put(numbers[i],i);
            }else {
                return new int[]{hash.get(tmp) + 1, i + 1};
            }
        }
        return arr;
    }

    /**
     * 数组中出现次数超过一半的数字
     */
    public int MoreThanHalfNum_Solution (int[] numbers) {
        // write code here
        HashMap<Integer, Integer> hash = new HashMap<>();
        for(int i = 0; i < numbers.length; i++) {
            if(!hash.containsKey(numbers[i])) {
                hash.put(numbers[i],1);
            }else {
                hash.put(numbers[i],hash.get(numbers[i]) + 1);
            }
            if(hash.get(numbers[i]) > numbers.length / 2) {
                return numbers[i];
            }
        }
        return 0;
    }
    /**
     * 数组中只出现一次的两个数字
     */
    public int[] FindNumsAppearOnce (int[] nums) {
        // write code here
        int[] arr = new int[2];
        HashMap<Integer, Integer> hash = new HashMap<>();
        for(int i = 0; i < nums.length; i++) {
            if(!hash.containsKey(nums[i])) {
                hash.put(nums[i], 1);
            }else {
                hash.put(nums[i], hash.get(nums[i]) + 1);
            }
        }
        int j = 0;
        for(int i = 0; i < nums.length; i++) {
            if(hash.get(nums[i]) == 1) {
                arr[j] = nums[i];
                j++;
            }
        }
        Arrays.sort(arr);
        return arr;
    }
    /**
     * 缺失的第一个正整数
     */
    public int minNumberDisappeared (int[] nums) {
        // write code here
        int n = nums.length;
        HashMap<Integer,Integer> hash = new HashMap<>();
        for(int i = 0; i < n; i++) {
            hash.put(nums[i], 1);
        }
        int ret = 1;
        while(hash.containsKey(ret)) {
            ret++;
        }
        return ret;
    }

    /**
     *  三数之和
     */
    public ArrayList<ArrayList<Integer>> threeSum (int[] num) {
        // write code here
        ArrayList<ArrayList<Integer>> ret = new ArrayList<>();
        int n = num.length;
        if(n < 3) {
            return ret;
        }
        //排序
        Arrays.sort(num);
        for(int i = 0; i < n - 2; i++) {
            if( i != 0 && num[i] == num[i - 1]) {
                continue;
            }
            //后续的收尾双指针
            int left = i + 1;
            int right = n - 1;
            //设置当前数的负值为目标
            int target = -num[i];
            while(left < right) {
                //双指针指向的二值相加为目标，则可以与num[i]组成0
                if(num[left] + num[right] == target) {
                    ArrayList<Integer> tmp = new ArrayList<>();
                    tmp.add(num[i]);
                    tmp.add(num[left]);
                    tmp.add(num[right]);
                    ret.add(tmp);
                    //去重
                    while(left + 1 < right && num[left] == num[left + 1]) {
                        left++;
                    }
                    while(right - 1 > left && num[right] == num[right - 1]) {
                        right--;
                    }
                    left++;
                    right--;
                }else if(num[left] + num[right] > target) {
                    right--;
                }else {
                    left++;
                }
            }

        }
        return ret;

    }



}
